Formulação do problema

• \(\mathbf{X}\) vetor aleatório em \(\mathbb{R}^p\) - preditores ou atributos (features)
• \(\mathcal{C}\) conjunto finito - rótulos
• \(Y\) variável aleatória em \(\mathcal{C}\) finito
• Distribuição de probabilidade conjunta para \((\mathbf{X}, Y)\)
• Observações \((\mathbf{X}_1, Y_1), \dots, (\mathbf{X}_n, Y_n), \dots \sim (\mathbf{X}, Y)\) iid

Formulação do problema

• Problema de predição: A partir de observações \((\mathbf{x}_i, y_i)_{i = 1, \dots, n}\) encontrar \(g: \mathbb{R}^p \to \mathcal{C}\) (dito o classificador) tal que \[``g(\mathbf{x}_{n + 1}) \approx y_{n + 1}, \dots, g(\mathbf{x}_{n + m}) \approx y_{n + m}"\]
• Como formular tal pergunta sem aspas?
• Como encontrar tal \(g\)?

Formulação do problema

• Risco esperado associado à \(g\): \[R(g) = \mathbb{E}[\underbrace{(Y - g(\mathbf{X}))^2}_{L(g; (\mathbf{X}, Y))}]\]
• “Basta” encontrar \(g\) que minimiza tal quantidade! :-)
• Tal procedimento é impossível… requer conhecimento completo do modelo probabilístico que relaciona \(\mathbf{X}\) com \(Y\)!
• Além disso, a perda quadrática \(L(g; (\mathbf{X}, Y)) = (Y - g(\mathbf{X}))^2\) não faz sentido no problema de classificação!

Formulação do problema

• Podemos trocar \[``g(\mathbf{x}_{i}) \approx y_{i}"\] por \[g(\mathbf{x}_{i}) = y_{i} \implies \text{:-)} \\ g(\mathbf{x}_{i}) \neq y_{i} \implies \text{:-(}\]

Formulação do problema

• Uma função perda razoável parece ser \[L(g; (\mathbf{X}, Y)) = \mathbb{I}(Y \neq g(\mathbf{X})) = \begin{cases} 0, &\text{ se } Y = g(\mathbf{X}) \\ 1, &\text{ se } Y \neq g(\mathbf{X}) \end{cases}\]
• Sua respectiva função risco é dada por \[R(g) = \mathbb{E}[\mathbb{I}(Y \neq g(\mathbf{X}))] = \mathbb{P}(Y \neq g(\mathbf{X}))\]
• Qual classificador \(g\) minimiza tal probabilidade?

O classificador de Bayes

Teorema: A função \(g: \mathbb{R}^p \to \mathcal{C}\) que minimiza o risco \[R(g) = \mathbb{E}[\mathbb{I}(Y \neq g(\mathbf{X}))] = \mathbb{P}(Y \neq g(\mathbf{X}))\] é o classificador de Bayes, dado por \[g(\mathbf{x}) = \mathop{\mathrm{argmax}}_{d \in \mathcal{C}} \mathbb{P}(Y = d | \mathbf{X} = \mathbf{x})\]

• Classificamos \(\mathbf{x}\) com a classe que possui a maior probabilidade a posteriori
• Porém, \(\mathbb{P}(Y = d | \mathbf{X} = \mathbf{x})\) é em geral desconhecida

Classifidadores plug-in

• Estimar \(\mathbb{P}(Y = d | \mathbf{X} = \mathbf{x})\) para cada classe \(d \in \mathcal{C}\)
• Considerar o classificador \[g(\mathbf{x}) = \mathop{\mathrm{argmax}}_{d \in \mathcal{C}} \widehat{\mathbb{P}}(Y = d | \mathbf{X} = \mathbf{x})\]
• Alguns exemplos:
  • Bayes ingênuo (Naive Bayes)
  • LDA/QDA
  • Regressão logística

Classificador Naive Bayes: atributos contínuos

• \(\mathbf{X} \in \mathbb{R}^p\) vetor de atributos - vetor aleatório contínuo com densidade \(q(\mathbf{x})\): \[\mathbb{P}(Y = d | \mathbf{X} = \mathbf{x}) = \frac{q(\mathbf{x} | Y = d)\mathbb{P}(Y = d)}{\sum_{c \in \mathcal{C}} q(\mathbf{x} | Y = c)\mathbb{P}(Y = c)}\]
• \(\mathbb{P}(Y = d)\) estimado através da proporção amostral entre as classes

Classificador Naive Bayes: atributos contínuos

• Assumir algum modelo probabilístico em \(\mathbf{X}\) para estimar \(q(\mathbf{x} | Y = d)\)
• Para toda classe \(d \in \mathcal{C}\), fatoramos \[q(\mathbf{x} | Y = d) = q(x_1, \dots, x_p | Y = d) = \prod_{j = 1}^{p} q(x_j | Y = d)\]
• Condicionalmente à classe \(Y\), as componentes de \(\mathbf{X}\) são independentes: hipótese ingênua - daí o nome!

Classificador Naive Bayes: atributos contínuos

• Para toda classe \(d \in \mathcal{C}\), fatoramos \[q(\mathbf{x} | Y = d) = q(x_1, \dots, x_p | Y = d) = \prod_{j = 1}^{p} q(x_j | Y = d)\]
• \(q(x_j | Y = d)\) pode ser qualquer distribuição de interesse
• Importância da análise exploratória preliminar!
• Importância de um bom “cinturão de utilidades” de modelos probabilísticos!

Classificador Naive Bayes: atributos contínuos

• Estimação de parâmetros (ou da forma de) \(q(x_j | Y = d)\):
  • Observações referentes ao atributo \(X_j\)…
  • …pertencentes à classe \(d\)
  • \(\Rightarrow\) ferramentas de Inferência Estatística!
  • Ou Inferência Não-Paramétrica, se for necessário
• No scikit-learn:
  • GaussianNB: \(X_j | (Y = d) \sim \mathrm{N}(\mu_{j, d}, \sigma_{j, d}^2)\)

Classificador Naive Bayes: atributos discretos

• Se \(\mathbf{X}\) é discreto, temos que: \[\mathbb{P}(Y = d | \mathbf{X} = \mathbf{x}) = \frac{\mathbb{P}(\mathbf{X} = \mathbf{x} | Y = d)\mathbb{P}(Y = d)}{\sum_{c \in \mathcal{C}} \mathbb{P}(\mathbf{X} = \mathbf{x} | Y = c)\mathbb{P}(Y = c)}\]
• \(\mathbb{P}(Y = d)\) estimado através da proporção amostral entre as classes
• Assumir algum modelo probabilístico em \(\mathbf{X}\) para estimar \(\mathbb{P}(\mathbf{X} = \mathbf{x} | Y = d)\)

Classificador Naive Bayes: atributos discretos

• Para toda classe \(d \in \mathcal{C}\), fatoramos \[\mathbb{P}(\mathbf{X} = \mathbf{x} | Y = d) = \mathbb{P}(X_1 = x_1, \dots, X_p = x_p | Y = d)\] \[= \prod_{j = 1}^{p} \mathbb{P}(X_j = x_j | Y = d)\]
• Condicionalmente à classe \(Y\), as componentes de \(\mathbf{X}\) são independentes: hipótese ingênua!

Classificador Naive Bayes: atributos discretos

• Estimação de parâmetros análoga ao caso contínuo
• No scikit-learn:
  • BernoulliNB: \(X_j | (Y = d) \sim \mathrm{Bern}(p_{j, d})\)
  • CategoricalNB: \(X_j | (Y = d) \sim \mathrm{Cat}(k, p_1, \dots, p_k)\)
  • ComplementNB: Aprimoramento do MultinomialNB
  • MultinomialNB: Não assume independência! \(\mathbf{X} | (Y = d) \sim \mathrm{Multi}(n, k, p_1, \dots, p_k)\)

Recapitulando

• Teorema (Classificador de Bayes): A função \(g: \mathbb{R}^p \to \mathcal{C}\) que minimiza o risco \[R(g) = \mathbb{E}[\mathbb{I}(Y \neq g(\mathbf{X}))] = \mathbb{P}(Y \neq g(\mathbf{X}))\] é o classificador de Bayes, dado por \[g(\mathbf{x}) = \mathop{\mathrm{argmax}}_{d \in \mathcal{C}} \mathbb{P}(Y = d | \mathbf{X} = \mathbf{x})\]

Recapitulando

• Se \(\mathbf{X}\) é contínuo com densidade \(q(\mathbf{x})\), temos que: \[\mathbb{P}(Y = d | \mathbf{X} = \mathbf{x}) \propto q(\mathbf{x} | Y = d)\mathbb{P}(Y = d)\]
• Análise de discriminante: Não assumir independência nas componentes de \(\mathbf{X} | (Y = d)\), mas que seguem uma normal multivariada mais geral

A distribuição normal multivariada

\[\begin{align*} \mathbf{Z} \sim &N(\boldsymbol{\mu}, \boldsymbol{\Sigma}) \iff \\ &p(\mathbf{z}) = \frac{1}{\sqrt{(2 \pi)^p \det(\boldsymbol{\Sigma})}} \times \\ &\quad\quad\quad\exp\left(-\frac{1}{2} (\mathbf{z} - \boldsymbol{\mu})^T \boldsymbol{\Sigma}^{-1} (\mathbf{z} - \boldsymbol{\mu})\right) \end{align*}\] onde \(\mathbf{z}, \boldsymbol{\mu} \in \mathbb{R}^p\) e \(\boldsymbol{\Sigma}\) é uma matriz \(p \times p\) simétrica positiva-definida

A distribuição normal multivariada

[Wikipedia] Dados de uma normal bivariada com \(\boldsymbol{\mu} = \begin{bmatrix} 0 \\ 0\end{bmatrix}\) e \(\boldsymbol{\Sigma} = \begin{bmatrix} 1 & 3/5 \\ 3/5 & 2\end{bmatrix}\).

Análise de discriminante linear (LDA)

• Cada \(\mathbf{X} | (Y = d)\) pode ter médias distintas porém as classes compartilham a mesma matriz de covariância: \[\mathbf{X} | (Y = d) \sim N(\boldsymbol{\mu}_d, \boldsymbol{\Sigma})\]
• Parâmetros estimados por máxima verossimilhança: \[\begin{align*} \widehat{\boldsymbol{\mu}}_{d} &= \frac{1}{|\mathcal{C}_d|} \sum_{k \in \mathcal{C}_d} \mathbf{x}_{k} \\ \widehat{\boldsymbol{\Sigma}} &= \frac{1}{n} \sum_{d \in \mathcal{C}} \sum_{k \in \mathcal{C}_d} (\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)(\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)^T \end{align*}\]

Análise de discriminante linear (LDA)

• Parâmetros estimados por máxima verossimilhança: \[\begin{align*} \widehat{\boldsymbol{\mu}}_{d} &= \frac{1}{|\mathcal{C}_d|} \sum_{k \in \mathcal{C}_d} \mathbf{x}_{k} \\ \widehat{\boldsymbol{\Sigma}} &= \frac{1}{n} \sum_{d \in \mathcal{C}} \sum_{k \in \mathcal{C}_d} (\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)(\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)^T \end{align*}\]
  • \(\mathcal{C}_d\) são todas as observações de treinamento da classe \(d\)
  • \(\mathcal{C}\) são todas as classes

Análise de discriminante linear (LDA)

• Podemos então considerar o classificador plug-in: \[\begin{align*} g(\mathbf{x}) &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{\mathbb{P}}(Y = d | \mathbf{X} = \mathbf{x}) \\ &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{q}(\mathbf{x} | Y = d)\widehat{\mathbb{P}}(Y = d) \\ &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{\delta}_d(\mathbf{x}) \end{align*}\]
• \(\widehat{\delta}_d\) são as funções discriminante (linear em \(\mathbf{x}\)!): \[\widehat{\delta}_d(\mathbf{x}) = \widehat{\boldsymbol{\mu}}_d^T \widehat{\boldsymbol{\Sigma}}^{-1} \mathbf{x} - \frac{1}{2}\widehat{\boldsymbol{\mu}}_d^T \widehat{\boldsymbol{\Sigma}}^{-1} \widehat{\boldsymbol{\mu}}_d + \ln(\widehat{\mathbb{P}}(Y = d))\]

Análise de discriminante linear (LDA)

• \(\widehat{\delta}_d(\mathbf{x})\) lineares em \(\mathbf{x}\)
• As fronteiras de decisão \(\{\mathbf{x} | \delta_d(\mathbf{x}) = \delta_c(\mathbf{x})\}\) são hiperlanos em \(\mathbb{R}^p\)
• Vejamos uma ilustração

Análise de discriminante linear (LDA)

(Figura 4.6 de [ITSL]) Exemplo com três classes, dados normalmente distribuídos em cada classe, com \(p = 2\). Esquerda: Elipses que contém 95% da probabilidade para cada uma das três classes e linhas pontilhadas representam as fronteiras de decisão do classificador de Bayes; Direita: 20 observações de cada classe e fronteiras de decisão do classificador LDA (linha contínua).

Análise de discriminante quadrático (QDA)

• \(\mathbf{X} | (Y = d)\) tem sua própria média e matriz de covariância: \[\mathbf{X} | (Y = d) \sim N(\boldsymbol{\mu}_d, \boldsymbol{\Sigma}_d)\]
• Parâmetros estimados por máxima verossimilhança: \[\begin{align*} \widehat{\boldsymbol{\mu}}_{d} &= \frac{1}{|\mathcal{C}_d|} \sum_{k \in \mathcal{C}_d} \mathbf{x}_{k} \\ \widehat{\boldsymbol{\Sigma}}_d &= \frac{1}{|\mathcal{C}_d|} \sum_{k \in \mathcal{C}_d} (\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)(\mathbf{x}_k - \widehat{\boldsymbol{\mu}}_d)^T \end{align*}\]

Análise de discriminante quadrático

• Podemos então considerar o classificador plug-in: \[\begin{align*} g(\mathbf{x}) &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{\mathbb{P}}(Y = d | \mathbf{X} = \mathbf{x}) \\ &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{q}(\mathbf{x} | Y = d)\widehat{\mathbb{P}}(Y = d) \\ &= \mathrm{argmax}_{d \in \mathcal{C}} \widehat{\delta}_d(\mathbf{x}) \end{align*}\]
• \(\widehat{\delta}_d\) são as funções discriminante (quadráticas em \(\mathbf{x}\)!): \[\begin{align*} \widehat{\delta}_d(\mathbf{x}) &= -\frac{1}{2}\ln(\det(\widehat{\boldsymbol{\Sigma}}_d)) - \frac{1}{2} \mathbf{x}^T \widehat{\boldsymbol{\Sigma}}_d^{-1} \mathbf{x} \\ &+ \widehat{\boldsymbol{\mu}}_d^T \widehat{\boldsymbol{\Sigma}}_d^{-1} \mathbf{x} - \frac{1}{2}\widehat{\boldsymbol{\mu}}_d^T \widehat{\boldsymbol{\Sigma}}_d^{-1} \widehat{\boldsymbol{\mu}}_d + \ln(\widehat{\mathbb{P}}(Y = d)) \end{align*}\]

Análise de discriminante quadrático (QDA)

• \(\widehat{\delta}_d(\mathbf{x})\) quadráticas em \(\mathbf{x}\)
• As fronteiras de decisão \(\{\mathbf{x} | \delta_d(\mathbf{x}) = \delta_c(\mathbf{x})\}\) são superfícies quádricas em \(\mathbb{R}^p\)
• Vejamos uma ilustração

Análise de discriminante quadrático (QDA)

Figura 4.9 de [ITSL]) Fronteiras de decisão do classificador de Bayes (tracejado roxo), LDA (pontilhado preto) e QDA (linha verde contínua) com duas classes. Esquerda: \(\boldsymbol{\Sigma}_1 = \boldsymbol{\Sigma}_2\); direita: \(\boldsymbol{\Sigma}_1 \neq \boldsymbol{\Sigma}_2\).

LDA ou QDA: qual escolher?

Retirada da página do scikit-learn. Comparação entre LDA e QDA.

LDA ou QDA: qual escolher?

• \(K\) classes e \(p\) preditores
• LDA estima \(Kp + p(p + 1)/2\) parâmetros: \[\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_K ~ \mathrm{ e } ~ \boldsymbol{\Sigma}\]
• QDA estima \(Kp + Kp(p + 1)/2\) parâmetros: \[\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_K ~ \mathrm{ e } ~ \boldsymbol{\Sigma}_1, \dots, \boldsymbol{\Sigma}_K\]

LDA ou QDA: qual escolher?

• LDA estima menos parâmetros que QDA \(\implies\) menos flexível/maior viés
• Por outro lado, requer menos dados para seu treinamento \(\implies\) “menos sensível ao conjunto de dados”/menor variância
• QDA estima mais parâmetros que LDA \(\implies\) mais flexível/menor viés
• portanto requer mais dados para seu treinamento \(\implies\) “mais sensível ao conjunto de dados”/maior variância

LDA ou QDA: qual escolher?

• LDA pode ser melhor que QDA se “poucas” amostras de treinamento estão disponíveis
• QDA pode ser melhor se o conjunto de treinamento é “grande” ou a hipótese de \(\boldsymbol{\Sigma}\) constante é inverossímil